package leetcode3;


import java.util.*;

//复习算法
public class Day4 {



    //1.移动零
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int right = -1;//right左边为0元素
        for(int i=0;i<n;i++) {
            if(nums[i]!=0) {
                right++;
                int tmp = nums[i];
                nums[i] = nums[right];
                nums[right] = tmp;
            }
        }
    }


    //2.复写零
    public void duplicateZeros(int[] arr) {
        //1.定位到最后一个需要复写的数
        //2.处理dest边界 -- 提前复写
        //3.正常复写
        int n = arr.length;
        int cur = 0;//定义最后一个复写位置
        int dest  =-1;//定位到结果的最后一个位置
        while(cur < n) {
            if(arr[cur] != 0) dest++;
            else dest += 2;
            if(dest >= n-1) break;
            cur++;
        }
        //处理边界
        if(dest == n) {
            dest--;//让dest回到正常位置
            //复写
            arr[dest--] = arr[cur--];
        }
        //继续复习
        while(cur>=0) {
            if(arr[cur] == 0) {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }else {
                arr[dest--]=arr[cur--];
            }
        }
    }
    //3.有效的三角形个数
    public int triangleNumber(int[] nums) {
        //1.排序
        //2.固定一条边，枚举其他两条边
        int count=0;
        Arrays.sort(nums);
        for(int i=nums.length-1;i>=2;i--) { //固定好第三条边：c
            int left=0; //a
            int right = i-1; //b
            while(left<right) { //固定第二条边：b
                //组成三角形的条件:a+b>c
                if(nums[left] + nums[right] > nums[i]) {
                    count += (right-left); //a为最小值，那么[left+1,right-1]所有的边+b都符合
                    right--;
                }else {
                    left++; //最小边不满足，往右移动
                }
            }
        }
        return count;
    }

    //4.长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int len = 0,sum = 0,ret=0;

        for(int left=0,right=0;right<nums.length;right++) {
            sum += nums[right];
            while(sum >= target) {
                len = right-left+1;
                if(ret==0 || len<=ret) {//更新最终结果
                    ret = len;
                }
                sum -= nums[left++];
            }
        }
        return ret;
    }


    //5.回文排列
    public boolean canPermutePalindrome(String s) {
        //1.字符串长度为偶数时，需要全部成对出现才能组成回文
        //2.字符串为奇数时，只有一个成单

        int n = s.length(),sum = 0;
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<n;i++) {
            char ch  = s.charAt(i);
            if(map.getOrDefault(ch,0) == 0)  map.put(ch,1);
            else  map.put(ch,map.get(ch)+1);
        }
        //遍历集合，记录奇数个数
        for(Map.Entry<Character,Integer> entry:map.entrySet()) {
            if(entry.getValue() % 2 !=0) sum++;
        }

        if(sum<=1) return true;
        return false;
    }


    public static void main(String[] args) {
        int[] array  = {1,2,4,7,10,11,7,12,6,7,16,18,19};
        subSort(array);
    }
    //6.部分排序
    public static int[] subSort(int[] array) {
        int[] ret = {-1,-1};
        int n = array.length;
        if(n <= 1) return ret;
        int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
        int left=0,right=1;
        boolean bool=true;
        while (right<n){
            if(array[left] > array[right]) {
                min = Math.min(array[right],min);
                max = Math.max(array[left],max);
                bool=false;
            }
            right++;
            left++;
        }
        if(bool) return ret;
        left=0;right=n-1;
        while (right>=0) {
            if(max > array[right]) {
                ret[1]=right;
                break;
            }
        }
        while(left<n) {
            if(min < array[left]) {
                ret[0]=left;
                break;
            }
        }
        return ret;
    }

}
